The present invention relates to a method for accelerating prefix encoding of data by byte-based machines. Although directed principally at software-only implementations, the method also can be employed in hardware or hybrid software/hardware prefix coders. The invention achieves significant improvement in encoding speeds at the sacrifice of increased storage requirements.
Prefix coding finds application to text compression, still image compression, fax compression, video compression, telemetry and related disciplines. Huff-man codes are a popular family of prefix codes that possess the desirable property of minimizing the average code word length (hence, maximizing the compression ratio) for data with a known probability distribution. Adaptive Huffman codes extend this property to situations in which the probabilistic mechanism governing the source output is not known a priori but can be estimated as the data stream unfolds.
Modifications of Huffman type prefix codes have been adopted in the widely deployed Group 3 and Group 4 facsimile standards and JPEG, H.263, H.320 and MPEG image and video standards. Common modifications include shortening the lengths of some of the Huffman code words for highly unlikely source symbols, protecting certain key code words (e.g., those representing end-of-line or end-of-block characters) from being misconstrued in the event that errors infiltrate the encoded bit stream during storage or transmission, bounding the maximum number of times in a row that a code symbol can be repeated in legitimately coded data in order to help maintain synchronization, ensuring that certain unique synchronizing sequences occur relatively frequently, forcing all code words to end with the same symbol, etc. The resulting so-called Modified Huffman codes sacrifice some of the compression ratio that would be achieved by a true Huffman code in order to provide one or more other properties deemed highly desirable in a given application.
The fact that successive code words having variable lengths get concatenated during prefix encoding makes prefix decoding an inherently bit-serial operation. More particularly, prefix decoding cannot be parallelized unless compression ratio is sacrificed by separating portions of the code stream from one another by a pattern of flag bits. Accordingly, prefix coding threatens to act as a bottleneck, especially in low-latency applications such as video conferencing, distance learning and telemedicine. The point is that, even though the bulk of the computations that need to be performed during the compression and decompression of images and video are devoted to two-dimensional transformation and motion estimation/compensation of image blocks, these computations can be parallelized in order to meet system latency requirements, but the prefix coding cannot.
This difficulty could be eliminated by using fixed-length rather than variable length codes, but then all the data compression ability would be lost with the likely result that whatever computational time might thus have been saved would be lost back during transmission. Hence, the efficient implementation of prefix encoding and decoding is a key component of the design of systems involving data compression, especially when a low latency requirement is imposed.
The bit-serial nature of prefix coding is particularly debilitating when the computations are performed by byte-based machines such as microprocessors or general purpose computers as opposed to by special purpose hardware. For example, whereas digital hardware can right-shift a bit stream in about a nanosecond, today's byte-based machines need to perform approximately a dozen logical operations in order to accomplish this, each of which requires several machine cycles; therefore, even a machine clocked as fast as 200 MHZ will require between ten and a hundred times longer to bit shift a data stream than would special-purpose digital hardware.
Nonetheless, there are compelling reasons to perform prefix coding on byte-based machines. One is that compression systems can be marketed and distributed nearly for free via the Internet and the world wide web provided they are software-only. Another is that it is easier to adapt to the statistics of the specific data sources one encounters in practice if the code is realized in software as opposed to hardware. Moreover, computer platforms today frequently receive compressed fax, image and video files via either downloads or external drives. In many applications there is a need to retrieve and display such material quickly. In such instances it would be advantageous to use byte-based techniques to decode the prefix-encoded portions of the compressed representations, even though such applications are not low-latency ones in which the encoding has been done only fractions of a second earlier. The gap between bytes and bits in software implementation of prefix decoders often has been bridged by means of stored, byte-addressable look-up tables; sometimes provision is made to update these tables in accordance with the empirically observed source statistics.
Although the gap between bits and bytes in prefix encoders also could be bridged similarly by means of stored encoding tables, this has not been done in practice. One reason is that many applications involve multicasting, i.e, are characterized by one encoder/transmitter servicing many decoders/receivers, as in the cases of web servers and video-on-demand. In such instances the encoder is an expensive, high-powered machine that is likely to contain special-purpose digital hardware to perform the prefix encoding operations. Another is that image and especially video encoding is so computationally demanding that encoders for low latency operations have had to be realized via special purpose hardware in order to keep up with the data stream. Hence, whereas software-only decoders (e.g., ones compatible with the MPEG1, MPEG2, H.261 and H.320 video decoding standards) have been implemented and widely disseminated, software-only encoders have not. However, rising interest in duplex, low-latency video applications such as teleconferencing, distance learning and telemedicine, coupled with increasing computer speeds and/or new encoding algorithms of considerably reduced complexity, have combined to make software-only encoding a viable endeavor. A need has therefore been created for a byte-based software-only encoding scheme for prefix encoding data streams. The present invention meets this need.